package com.cat.binaryTree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/unique-binary-search-trees-ii/?envType=problem-list-v2&envId=dynamic-programming
 * @create 2025/9/30 14:50
 * @since JDK17
 */

public class Solution93 {
    List<TreeNode> dfs(int l, int r) {
        if (l > r) {
            // 一个继承了ArrayList的匿名类
            return new ArrayList<>() {{
                add(null);
            }};
        }
        List<TreeNode> list = new ArrayList<>();
        for (int i = l; i <= r; i++) {
            for (var left : dfs(l, i - 1)) {
                for (var right : dfs(i + 1, r)) {
                    list.add(new TreeNode(i, left, right));
                }
            }
        }
        return list;
    }

    public List<TreeNode> generateTrees(int n) {
        return dfs(1, n);
    }
}
